package com.ddd.demo.lee.排序;

public class 计数排序 {

    public static void countingSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }

        // 1. 得到数列的最大值和最小值，并算出差值 d
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        int d = max - min;

        // 2. 创建统计数组并计数
        int[] countArray = new int[d + 1];
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i] - min]++;
        }

        System.out.println("1111111111");
        for (int i : countArray) {
            System.out.print(i + " ");
        }

        // 3. 统计数组做变形，后面的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }
        System.out.println();
        System.out.println("22222222");
        for (int i : countArray) {
            System.out.print(i + " ");
        }

        System.out.println();
        // 4. 倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
        int[] sortedArray = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArray[countArray[arr[i] - min] - 1] = arr[i];
            countArray[arr[i] - min]--;
        }

        // 5. 将有序数组覆盖到原数组
        System.arraycopy(sortedArray, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {3, 0, 2, 5, 4, 1, 3, 2, 5, 6, 0, 8, 7, 1, 9};
        countingSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

}
